广度优先搜索

广度优先搜索属于图算法的一种，英文缩写为 BFS 即 Breath First Search。其过程是每一次都遍历完所有的子分支之后，再去遍历所有子分支的子分支，也就是一层一层去遍历。

和深度优先搜索对应，宽度优先搜索虽然也是遍历全局，但是遍历的方式是像波浪一样一层一层向外拓展的，而不是一头走到黑。

示例

全排列

给定一个整数 n，将数字 1~n 排成一排，将会有很多种排列方法。 现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。 数据范围 1≤n≤7

输入样例

3

输出样例

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

下面是使用队列的方式来实现广度优先搜索。

可以和使用栈的深度优先搜索对比，其结构是类似的。

from collections import deque
def bfs(node):
    for i in range(1, n + 1): #队列先进先出，所以小的先进，先出。
        if i not in node:
            queue.append(node + [i])
            #print(queue) #取消注释，查看stack的变化过程

n = int(input())
root = []
queue = deque([root])
while queue:
    node = queue.popleft()
    if len(node) == n:
        print(node)
    bfs(node)

总结

广度优先搜索也算是一种暴力枚举，不过有时候我们可以使用剪枝和记忆化的方式来减少搜索次数，从而提升效率。

适用问题：

• 最短路径

代码模板

from collections import deque
def bfs(node):
    for child in children: #children是根据node得到的所有子节点
        if valid(child):
            queue.append(child)

queue = deque([root]) #root是根节点
while queue:
    node = queue.popleft()
    bfs(node)

练习